pub fn dp_rec_mc(amount: u32) -> u32 {
    // TODO: 这里写逻辑
    // 动态规划方法，先计算 base case 最小找零情况 即找零 0元
    // 然后从找零金额小到大，继续找最少找零数量，并记录到dp_table
    // 递推到最后 就知道 找零 amount 需要的最少找零纸币数量了

    let caches = [1, 2, 5, 10, 20, 30, 50, 100];
    // dp 数组初始化成 0, 只有base case 才真的是需要0，其他的0都不合法，后续需要更新
    let mut dp_table:Vec<u32> = vec![0;amount as usize + 1];
    // dp_table.fill(0);
    // println!("{}",dp_table.len());
    // let mut min_cache_times = 101;
    // 从小到大递推
    for num in 1..=amount{
        // 基本面就是都用1元的来找零，所以需要 num 个一元纸币
        let mut min_cache_times = num;

        // 大于剩余找零金额的面额的纸币没必要参加
        for cache in caches.iter()
                            .filter(|&&cache| cache <= num)
                            .collect::<Vec<&u32>>(){

            let left = (num - cache) as usize; // 用了当前这张纸币，剩余金额left
            // 1(用掉的这一张) + 剩余金额需要的找零的最小数量
            // 因为从小到大递推的，所以 dp_table[left] 一定是有值的，且是最优解
            let cache_num = 1 + dp_table[left];
            
            min_cache_times = min_cache_times.min(cache_num); // 如果这个方案更好，就保存
        }
        // 一轮查询后 保存最优答案
        dp_table[num as usize] = min_cache_times;
    }
    // 最后返回对应的值，就是最优解
    dp_table[amount as usize]
}
